#include <string>
using std::string;
class Solution
{
public:
    int numDecodings(string s)
    {
        // 状态表示 dp[i] s[i]的解码数量
        // 状态转移方程  要么被单独解释 成功 dp[i-1] 失败 0
        //              要么和上一个一起解释 成功 dp[i-2] 失败 0
        //              i的解码数量等于单独解释数量+上一个一起解释数量
        //              dp[i]=dp[i-1]+dp[i-2]
        // 初始化 dp[-1]==0 dp[0]==1
        if (s[0] == '0')
            return 0;
        int dp0 = 1, dp1 = 1;
        char ch1 = s[0];
        for (int i = 1; i < s.size(); i++)
        {
            bool sig = !(s[i] == '0');
            int dou_num = (s[i - 1] - '0') * 10 + s[i] - '0';
            bool dou = dou_num >= 10 && dou_num <= 26;
            int dpi = 0;
            if (sig)
                dpi += dp1;
            if (dou)
                dpi += dp0;
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }
};